/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * HashJoinMap.java
 * ---------------------------
 *
 */
package algos;

import java.util.Arrays;
import java.util.Iterator;

/**
 * Map for the use in a Hash join algorithm.
 * <p>
 * This map support only additions; also, it doesn't accept null values as keys,
 * because two null fields are not considered equal, so the adding record
 * doesn't need to be added to the map.<br>
 * A simple chaining algorithm is used, and rehashing triggers when the
 * keys/bucket ratio is greater than DFLT_FILL_FACTOR.
 * <p>
 * <b>WARNING</b> this map doesn't set a maximum number, but i can be very easily
 * implemented; also it doesn't implement modification verify, but it not
 * interesting.
 * <p>
 * This map doesn't internally implement generics because it's just oriented to
 * hash joins.<br>
 * It's quite easy to implement them anyway, with the aid of
 * Array.newInstance(); also, for creating a really generic solution (including
 * primitives) we must use Array.set() instead of direct assignation, which
 * quite s*cks.<br>
 * Actually, Java generic implementation is very poor for design choices, but
 * that's the only possible way.
 *
 * @author Saverio Miroddi
 */
public class HashJoinMap<K, V> {
	private static final float DFLT_FILL_FACTOR = 0.75f;

	private Value<V>[] buckets;
	private int filledBuckets;
	/* threshold for growin' da array! */
	private int currTreshold;

	/**
	 * Main constructor
	 *
	 * @param startElements
	 *            number of starting elements. <b>Warning:</b> this differs from
	 *            HashMap start capacity, because this takes the elements and
	 *            computes the starting capacity basing on fill factor, while
	 *            HashMap directly sets the capacity.
	 * @param fillFactory
	 */
	@SuppressWarnings("unchecked")
	public HashJoinMap(int startElements) {
		int startCapacity = (int)Math.ceil(startElements / DFLT_FILL_FACTOR);
		startCapacity = roundToPowerOfTwo(startCapacity);

		currTreshold = (int)(startCapacity * DFLT_FILL_FACTOR);

		this.buckets = new Value[startCapacity];
		this.filledBuckets = 0;
	}

	/**
	 * Funny routine.
	 */
	private int roundToPowerOfTwo(int i) {
		int nextTwoPower = 1;
		while (i > nextTwoPower) nextTwoPower <<= 1;
		return nextTwoPower;
	}

	/**
	 * Add a value with the specified key.
	 *
	 * @param key
	 *            key
	 * @param value
	 *            value
	 */
	public void add(K key, V value) {
		if (key == null) throw new IllegalArgumentException("Null keys not accepted");

		Value<V> bucket = new Value<V>(key, value);
		addValue(buckets, bucket);

		/* It's possible to opt. by checking rehashing before inserting the
		 * new value */
		rehashIfNeeded();
	}

	/**
	 * Add a value to a map, computing its hash and addind it to the
	 * appropriate linked list.
	 *
	 * @param bucketsArr
	 *            map (array of linked lists).
	 * @param value
	 *            value to add.
	 */
	private void addValue(Value<V>[] bucketsArr, Value<V> value) {
		/* Slower but cleaner. With MUCH attention, can be easily opt.
		 * [removed]. */
		Value<V> newValue = new Value<V>(value);

		int pos = newValue.key.hashCode() % buckets.length;

		Value<V> oldBucket = bucketsArr[pos];

		if (oldBucket == null) filledBuckets++;

		newValue.next = oldBucket;

		bucketsArr[pos] = newValue;
	}

	/**
	 * Rehash if the fill factor surpass the predefined one.
	 */
	private void rehashIfNeeded() {
		// known hash attack vulnerable ;-)
		while (filledBuckets > currTreshold) {
			filledBuckets = 0;

			@SuppressWarnings("unchecked")
			Value<V>[] newBuckets = new Value[buckets.length << 1];

			for (Value<V> value: buckets) {
				while (value != null) {
					addValue(newBuckets, value);
					value = value.next;
				}
			}

			buckets = newBuckets;
			currTreshold = (int)(buckets.length * DFLT_FILL_FACTOR);
		}
	}

	/**
	 * Return the iterator for the values corresponding to the specific key.
	 *
	 * @param key
	 *            key
	 * @return iterator for the values.
	 */
	public Iterator<V> values(final K key) {
		/* used as internal class for easier debug */
		class BucketIterator implements Iterator<V> {
			/** this is not null before the first record of after the last */
			private Value<V> currValue;
			/** force hasNext to search the next matching record */
			private boolean searchNext;

			private BucketIterator() {
				int pos = key.hashCode() % buckets.length;
				this.currValue = buckets[pos];
				searchNext = false;
			}

			@Override
			public boolean hasNext() {
				if (currValue == null) {
					return false;
				}
				// if not search next, we look at the current value,
				// if it match return true, otherwise search next.
				else if (! searchNext && currValue.key.equals(key)) {
					return true;
				}

				do {
					currValue = currValue.next;
				} while (currValue != null && ! currValue.key.equals(key));

				searchNext = false;

				return currValue != null;
			}

			@Override
			public V next() {
				if (currValue != null) {
					searchNext = true;
					return currValue.value;
				}
				else {
					throw new IllegalStateException("No next value!");
				}
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException("Remove not supported.");
			}
		}

		return new BucketIterator();
	}

	/**
	 * Debug.
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();

		int count = 0;

		boolean isFirstBucket = true;

		for (Value<V> value: buckets) {
			if (value != null) {
				if (! isFirstBucket) sb.append('\n');
				else isFirstBucket = false;

				sb.append(value.key).append(':');
				boolean isFirstValue = true;

				while (value != null) {
					count++;
					if (! isFirstValue) sb.append(',');
					else isFirstValue = false;

					sb.append(value);

					value = value.next;
				}
			}
		}

		sb.insert(0, "[" + count + "] ");

		return sb.toString();
	}

	/**
	 * Element of the bucket (linked list).
	 */
	private static class Value<V> implements Cloneable {
		public Value<V> next;
		public Object key;
		public V value;

		public Value(Object key, V value) {
			this.key = key;
			this.value = value;
		}

		/**
		 * Copy constructor.<br>
		 * Retains only key and value variables.
		 */
		public Value(Value<V> other) {
			this.key = other.key;
			this.value = other.value;
		}

		/** Debug. */
		@Override
		public String toString() {
			if (value == null) {
				return null;
			}
			else {
				if (value.getClass().isArray()) return Arrays.toString((Object[])value);
				else return value.toString();
			}
		}
	}
}
